import sortedcontainers
class MedianFinder(object):

    def __init__(self):
        self.stack = sortedcontainers.SortedList()
        self.n = 0
    def addNum(self, num):
        """
        :type num: int
        :rtype: None
        """
        self.stack.add(num)
        self.n += 1

    def findMedian(self):
        """
        :rtype: float
        """
        if self.n % 2 == 0:
            return (self.stack[self.n // 2 - 1] + self.stack[self.n // 2]) / 2
        else:
            return self.stack[(self.n - 1) // 2]

